6.1 KB · ⇊ 2 parts · ⤓ Micron 6.1 KB · ⤓ HTML 15.6 KB

top

Un mwawregistro a scorrimento a retroazione con riporto, generalmente indicato come mwbaFCSR, sigla di mwbqFeedback with Carry Shift Registers, è un tipo di registro simile al mwbgRegistro a scorrimento a retroazione lineare (o LSFR) da cui differisce per la presenza di un registro secondario per la memorizzazione del riporto, o resto delle operazioni. Se N > 1 è un mwbwintero allora l'N-adico FCSR di lunghezza mwcar è un dispositivo a stato finito con uno stato mwcq(a;z) = (amwcg0,amwcw1,...,amwdar-1;z) costituito da un mwdqvettore di elementi mwdgamwdwi appartenenti a mwea{0,1,...,N-1}=S ed un intero mweqzcite-ref-fcsr1-1-0[1]cite-ref-2[2]cite-ref-book-3-0[3]cite-ref-efficient-mwc-4-0[4]. L'operazione di cambio di stato è determinata da un insieme di coefficienti mwigqmwiw1,...,qmwjan ed è definita come segue: calcolare mwjqs = qmwjgramwjw0+qmwkar-1amwkq1+..+qmwkg1amwkwr-1 + z. Esprimere mwlas come mwlqs = amwlgr+Nz' con mwlwamwmar appartenente ad mwmqS. Il nuovo stato è quindi mwmg(amwmw1,amwna2,...,amwnqr;z'). Iterando il cambiamento di stato un FCSR genera un'infinita, eventualmente anche periodica, sequenza di numeri in mwngS.

Gli FCSR sono utilizzati nei mwoacifrari a flusso (ad esempio nell'mwoqF-FCSR), nella mwogcrittanalisi del mwowsummation generator (una primitiva mwpacrittografica creata nel mwpq1985) e come mwpggeneratore di numeri pseudo casuali nel mwpwmetodo Quasi Monte Carlo (sotto il nome di "generatore mwqaMultiply With Carry (MWC)", inventato da Couture e L'Ecuyercite-ref-5[5], generalizzando un lavoro di Marsaglia e Zamancite-ref-mz-6-0[6].

Gli FCSR sono analizzati utilizzando la mwsgteoria dei numeri. Associato all'FCSR c'è un intero di connessione mwswq = qmwtarNmwtqr + ... + qmwtg1N - 1. Associato alla sequenza di output c'è il numero N-adico mwtwa = amwua0 + amwuq1N + amwug2Nmwuw2+.... Il teorema fondamentale degli FCSR afferma che c'è un intero mwvau tale che mwvqa = u/q, un numero razionale. La sequenza di output è strettamente periodica se e soltanto se mwvgu è compreso fra mwvw-q e 0. È possibile esprimere mwwau come un polinomio quadratico semplice che coinvolge lo stato iniziale e mwwqqmwwgicite-ref-fcsr1-1-1[1].

C'è anche una rappresentazione esponenziale degli FCSR: se mwyag è l'inverso di mwyqN modulo q, e la sequenza di output è strettamente periodica, allora mwygamwywi = (Agmwzai mod q) mod N, dove mwzqA è un intero. Ne consegue che il periodo è al massimo dell'ordine di mwzgN nel gruppo moltiplicativo di unità modulo mwzwq. Questo vale ancor di più quando mwaaq è primo e mwaqN è un mwagelemento primitivo modulo mwawq. Allora il periodo è mwbaq-1: in questo caso la sequenza di output è chiamata mwbqsequenza-l, mwbgsequenza lunga (o mwbwl-sequence).

cite-note-fcsr1-11. ↑ A. Klapper and M. Goresky, mweaFeedback Shift Registers, 2-Adic Span, and Combiners With Memory, in Journal of Cryptology vol. 10, pp. 111-147, 1997, mweq

cite-note-22. ↑ R. Couture and P. L'Ecuyer, mwfqOn the lattice structure of certain linear congruential sequences related to AWC/SWB generators, Math. Comp. vol. 62, pp. 799–808, 1994, mwfg,

cite-note-book-33. ↑ M. Goresky and A. Klapper, mwggAlgebraic Shift Register Sequences, 2009, mwhqmwhg

cite-note-efficient-mwc-44. ↑ M. Goresky and A. Klapper, mwkqEfficient Multiply-with-Carry Random Number Generators with Optimal Distribution Properties, ACM Transactions on Modeling and Computer Simulation, vol 13, pp 310-321, 2003, mwkg

cite-note-55. ↑ R. Couture, P. L'Ecuyer: mwlgOn the lattice structure of certain linear congruential sequences related to AWC/SWB generators, Math. Comp. vol. 62, pagg. 799–808, mwlw1994, mwma,

cite-note-mz-66. ↑ G. Marsaglia, A. Zaman: mwnaA new class of random number generators, Annals of Applied Probability, vol. 1, pagg. 462–480, 1991